package solution._0030._0037;

import java.util.ArrayList;

/**
 * Created by chen_snow
 * Date: 2021/6/21 23:30
 * Description:  解数独
 */
public class Solution {
    public void solveSudoku(char[][] board) {
        ArrayList<int[]> data = new ArrayList<>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '.') {
                    data.add(new int[]{i, j});
                }
            }
        }

        backTrace(board, data, 0);
    }

    public boolean backTrace(char[][] board, ArrayList<int[]> data, int num) {
        if (data.size() == num) {
            return true;
        }

        int[] array = data.get(num);
        ArrayList<Integer> options = calculate(board, array[0], array[1]);

        for (int i = 0; i < options.size(); i++) {
            board[array[0]][array[1]] = (char) (options.get(i) + '0');
            if (backTrace(board, data, num + 1)) {
                return true;
            }
            board[array[0]][array[1]] = '.';
        }

        return false;
    }

    public ArrayList<Integer> calculate(char[][] board, int row, int column) {
        ArrayList<Integer> chooses = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            if (board[row][i] != '.' && !chooses.contains(board[row][i])) {
                chooses.add(board[row][i] - '0');
            }
        }

        for (int i = 0; i < 9; i++) {
            if (board[i][column] != '.' && !chooses.contains(board[i][column])) {
                chooses.add(board[i][column] - '0');
            }
        }

        int rowIndex = row / 3;
        int columnIndex = column / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[rowIndex * 3 + i][columnIndex * 3 + j] != '.'
                        && !chooses.contains(board[rowIndex * 3 + i][columnIndex * 3 + j])) {
                    chooses.add(board[rowIndex * 3 + i][columnIndex * 3 + j] - '0');
                }
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            if (!chooses.contains(i)) {
                result.add(i);
            }
        }
        return result;
    }
}
